package com.zwj.interview.链表;

import com.zwj.interview.链表.ListNode;

/**
 * 输入一个链表的头节点，请将该链表排序
 */
@Deprecated
public class 单链表排序 {


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode head1 = head;
        //拿到后半部分的起点
        ListNode head2 = split(head);
        head1 = sortList(head1);
        head2 = sortList(head2);
        return merge(head1, head2);
    }

    /**
     * 如果慢指针一次走一步，快指针一次走两步，当快指针走到链表尾部时，
     * 慢指针只走到链表的中央，这样也就找到了链表后半部分的头节点
     */
    private ListNode split(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        //快慢指针，满指针走一步，快指针走两步
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //拿到链表后半部分的起点，并断开链表,有的地方是ListNode second = slow，写出等slow是中点，slow.next是后半部分的起点
        ListNode second = slow.next;
        slow.next = null;
        return second;
    }

    //合并两个链表
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        //当任意一个链表走完的时候,就将当前节点的next指针指向没走完的节点
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }









}
